#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct Nene
{
	struct node
	{
		int nxt,to;
	}e[500005<<1];
	int head[500005],cnt_edge;
	void add_edge(int u,int v)
	{
		e[++cnt_edge].to=v;
		e[cnt_edge].nxt=head[u];
		head[u]=cnt_edge;
	}
}T,G;
namespace Tarjan
{
	int low[500005],dfn[500005],stk[500005],top,cnt;
	int dcc[500005],cnt_dcc;
	void tarjan(int u,int fa)
	{
		low[u]=dfn[u]=++cnt;
		stk[++top]=u;
		for(int i=G.head[u];i;i=G.e[i].nxt)
		{
			int v=G.e[i].to;
			if(!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
			else if(v!=fa) low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u])
		{
			++cnt_dcc;
			while(stk[top+1]!=u) dcc[stk[top--]]=cnt_dcc;
		}
	}
}
using Tarjan::tarjan;
using Tarjan::dcc;
int n,m,k,r;
int f[500005],siz[500005],son[500005],dep[500005],top[500005];
int sum[500005];
int deg[500005];
int ans,cmx,mx;
void dfs1(int u,int fa)
{
	f[u]=fa;siz[u]=1;dep[u]=dep[fa]+1;
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	if(son[u]) dfs2(son[u],t);
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
void dfs3(int u)
{
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==f[u]) continue;
		dfs3(v);
		sum[u]+=sum[v];
	}
	if(sum[u]>=mx) cmx=mx,mx=sum[u];
	else cmx=max(cmx,sum[u]);
}
inline int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=f[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int cx[500005];
int main()
{
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	n=read(),m=read(),k=read(),r=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		++deg[u];++deg[v];
		G.add_edge(u,v);G.add_edge(v,u);
	}
	tarjan(1,0);
	for(int i=1;i<=n;i++) 
		for(int j=G.head[i];j;j=G.e[j].nxt)
		{
			int u=G.e[j].to;
			if(dcc[u]!=dcc[i]) T.add_edge(dcc[i],dcc[u]);
		}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=k;i++)
	{
		int u=read(),v=read();
		++cx[u];++cx[v];
		++sum[dcc[u]],++sum[dcc[v]],sum[lca(dcc[u],dcc[v])]-=2;
	}
	dfs3(1);
	ans=r==2?cmx+mx:mx;
	for(int i=1;i<=n;i++) 
		if(deg[i]<=r) ans=max(ans,cx[i]);
	write(ans);
	return 0;
}
